package main

import (
	"fmt"
)

func findMaxY(arr []int) int {
	length := len(arr)
	if length <= 1 {
		return arr[0]
	} else {
		max := arr[0]

		for i := 1; i < len(arr); i++ {
			if max < arr[i] {
				max = arr[i]
			}
		}

		return max
	}

}

// 统计排序
func countSort(arr []int) []int {
	max := findMaxY(arr)

	fmt.Println(max)

	countArr := make([]int, len(arr))

	//分组个数
	for _, v := range arr {
		countArr[v]++
	}

	//叠加
	for i := 1; i <= max; i++ {
		countArr[i] += countArr[i-1]
	}

	sortArr := make([]int, len(arr))

	// 循环数组
	for _, v := range arr {
		sortArr[countArr[v]-1] = v
		countArr[v]--
	}

	fmt.Println(sortArr)

	return sortArr
}

func main() {
	arr := []int{1, 2, 3, 4, 4, 3, 2, 1, 2, 5, 5, 3, 4, 3, 2, 1}

	countSort(arr)
}
